package cn.edu.jxau.test;

import java.util.Arrays;

public class MaxPQ {

    public static void main(String[] args) {

        MaxPQ maxPQ = new MaxPQ(new char[]{'E','A','S','Y','Q','U','E','S','T','I','O','N'});
        System.out.println(maxPQ.delMax());
        System.out.println(maxPQ.delMax());
        System.out.println(maxPQ.delMax());
        System.out.println(maxPQ.delMax());
        System.out.println(maxPQ.delMax());
        System.out.println(maxPQ.delMax());
        System.out.println(maxPQ.delMax());
        System.out.println(maxPQ.delMax());
        System.out.println(maxPQ.delMax());
        System.out.println(maxPQ.delMax());
        System.out.println(maxPQ.delMax());
        System.out.println(maxPQ.delMax());
    }

    /**
     * 堆
     */
    private char[] pq;

    /**
     * 堆中元素个数
     */
    private int size;

    /**
     * 初始大小
     */
    private static final int INIT_CAPACITY = 10;

    public MaxPQ() {

        pq = new char[INIT_CAPACITY];
    }

    public MaxPQ(char[] charArr) {

        pq = new char[charArr.length + 1];
        for (int i = 0; i < charArr.length; i++) {
            pq[i + 1] = charArr[i];
        }
        size = charArr.length;
        // sink构造堆 //
        for (int i = pq.length / 2; i >= 1; i--) {
            sink(i);
        }
        System.out.println(Arrays.toString(charArr));
        
    }

    public void insert(char ch) {

        if (size == pq.length - 1) {
            resize(pq.length * 2);
        }
        pq[++size] = ch;
        swim(size);
    }

    private void resize(int newCapacity) {

        if (newCapacity < INIT_CAPACITY) { // 防止优先队列缩减得过小
            return;
        }
        System.out.println("resize to " + newCapacity);
        char[] tempPQ = new char[newCapacity];
        for (int i = 1; i <= size; i++) {
            tempPQ[i] = pq[i];
        }
        pq = tempPQ;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public char max() {

        if (isEmpty()) {
            throw new RuntimeException("优先队列为空");
        }
        return pq[1];
    }

    public char delMax() {

        char max = max();
        swap(1, size);
        size--;
        sink(1);
        if (size * 4 < pq.length) {
            resize(pq.length / 2);
        }
        return max;
    }

    private void swap(int i, int j) {

        char temp = pq[i];
        pq[i] = pq[j];
        pq[j] = temp;
    }

    private void swim(int k) {

        while (k > 1 && pq[k] > pq[k / 2]) {
            swap(k, k / 2);
            k /= 2;
        }
    }

    private void sink(int k) {

        while (2 * k <= size) {

            int i = 2 * k;
            if (i < size && pq[i] < pq[i + 1]) {
                i++;
            }
            if (pq[k] >= pq[i]) {
                break;
            }
            swap(k, i);
            k = i;
        }
    }
}
